package 栈与队列;

/**
 * 222. 完全二叉树的节点个数
 *
 * 思路：
 *   首先我们要利用完全二叉树的性质来优化时间复杂度，完全二叉树的子树中至少有一个是满二叉树，这使得我们可以递归地计算节点数，而不需要遍历所有节点，
 * 解题方案：
 *   1.完全二叉树的性质，若左子树的高度等于右子树的高度，则左子树是满二叉树，右子树是完全二叉树；否则，右子树是满二叉树，左子树是完全二叉树。
 *   2.计算高度： 通过遍历左子树节点直接叶子节点来计算左子树的高度。
 *   3：递归计算: 根据左右子树的高度判断哪边是满二叉树，直接计算满二叉树的节点数，再递归计算另一个子树的节点数。
 *
 */
public class L_222 {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        // 如果leftHeight等于rightHeight，说明左子树是满二叉树，右子树是完全二叉树
        // 节点数为2^leftHeight -1，加上右子树的节点数和根节点
        if(leftHeight == rightHeight){
            return (1 << leftHeight) + countNodes(root.right);
        }else {
            // 否则，说明右子树是满二叉树，左子树是完全二叉树
            // 节点数为2^rightHeight -1，加上左子树的节点数和根节点
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    // 计算当前子树的高度
    private int getHeight(TreeNode root){
        int height = 0;
        while (root != null){
            height++;
            root = root.left;
        }
        return height;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
